\chapter{相关工作}\label{chap:relate}

本章首先介绍了什么是Graphlet——一种图的局部结构，接着介绍了传统的基于kernel的图分类方法，比如随机游走kernel(Random Walk,RW),基于路径的kernel(Path-based),和Graphlet kernel。接着本文介绍了近年流行的图神经网络，比如图卷积神经网络和图注意力网络，还介绍了两种池化的方法diffPool和TopK。

\section{复杂网络及其高阶结构}

信息时代，数据之间的组织方式常以复杂网络的形式呈现，而复杂的网络往往会存在一些高频出现的局部特征，如果能把握住这些局部特征，就可以对复杂的网络有更好的表征，从而对图分类任务有更好的帮助。

下面我们介绍一种局部特征——Graphlets。

Graphlets是从一个大的图中诱导出来的一组非同构子图。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=1\textwidth]{Img/graphlets.png}
    \caption{Graphlets}
    \label{fig:graphlets}
\end{figure}

如图~\ref{fig:graphlets},选取不同节点个数的非同构子图可以得到不同的一组Graphlets，显然这样一组Graphlets是对图结构的某种反映。并且我们可以注意到，对于每一个子图，其上的节点考虑对称性的情况下具有确定的位置(角色)，而原图中的每一个节点，在包含其的不同的诱导子图中可能处于不同的位置，如果我们将其在所有包含它的诱导子图中所扮演的角色计数，可以得到一个关于不同角色个数的序列，称其为Graphlet Degree Vector\citep{tu2020learning,Ribeiro2017struc2vecLN,Adhikari2018Sub2VecFL}。

比如说在考虑3个节点的情况下，某个节点的Graphlet Degree Vector可以是(1,1,1)这说明其在所有包含它的三节点诱导子图中分别扮演~\ref{fig:graphlets}中角色1,2,3一次。

下面我们给出获得一个图的GDV的例子,本文实际使用的算法参见\citep{GDVCounting}.

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.6\textwidth]{Img/exGraph.png}
    \caption{一个具有十个节点的图}
    \label{fig:exGraph}
\end{figure}

\begin{table}[!htbp]
    \caption{\ref{fig:exGraph}中各个节点的4-Node的GDV}
    \label{tab:exGraphGDV}
    \centering
    \footnotesize% fontsize
    \setlength{\tabcolsep}{4pt}% column separation
    \renewcommand{\arraystretch}{1.2}%row space 
    \begin{tabular}{lccccccccccccccc}
    \toprule
                &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\
    \midrule
    Node0    & 9 &0& 15& 21& 0& 0& 0& 3& 0& 0& 0& 32& 0& 32& 17 \\
    Node1      & 8 &4 &10 &18 &0 &8 &0 &2 &1 &0 &8 &15 &5 &24 &15 \\
    Node2       &5 &12& 1& 9& 7 &3 &3 &0 &0 &8 &19 &0 &13 &3 &7\\    
    Node3     &4 &12& 1& 5& 14& 2& 1& 0& 2& 15& 12& 0& 9 &2 &2\\
    Node4    &5 &11& 1& 9& 11& 2& 3& 0& 0& 7& 16& 0& 13& 3 &7\\
    Node5     &5 &12& 2& 8& 6& 6& 2& 0& 1& 12& 16& 0& 12& 6 &4\\
    Node6    &5 &12& 1& 9& 7& 3& 3& 0& 0& 8& 19& 0& 13& 3 &7\\
    Node7    &6 &12& 5& 10& 3& 10& 3& 0& 3& 6& 12& 6& 16& 8 &6\\
    Node8    &7 &7& 6& 15& 1 & 8& 0& 1& 2& 3& 16& 6 &7 &15 &13\\
    Node9    &6 &12& 5& 10& 3& 10& 3& 0& 3& 6& 12& 6& 16& 8 &6\\
    \bottomrule
    \end{tabular}
    \end{table}

\section{基于图核的图分类方法}

    一般而言，我们要想比较两个图，有以下的方法:
    \begin{itemize}
        \item 比较两个图之间的点集$\mathcal{V}$和边集$\mathcal{E}$,这种方法的优势在于速度快，只需要线性或是二次的时间复杂度。但是它忽略了图具有的拓扑结构，因此通常在实践中不会使用这么简单的方法。
        \item 比较两个图的所有子图，这种方法考虑了图具有的拓扑结构并且能完美的比较两个图之间的不同，然而却带来了十分高的指数级别的复杂度。
        \item 使用图核(Graph Kernel)，这种方法实际上是在辨别精度和运行速度之间的一个trade-off。
    \end{itemize}

    通常而言，一个图核(Graph Kernel)是一个定义在两个图上的正定函数，通常表现为内积的形式。

    $$
        \mathcal{K}: \mathbb{G}\times\mathbb{G}\mapsto\mathbb{R}
    $$

    其中,$\mathbb{G}$是图所在的空间。

    如果我们获得了图kernel，就可以直接将图作为传统的Kernel-based的机器学习方法的输入，比如说支持向量机和混合高斯分布模型。由表示定理\citep{RepresenterTheorem}，我们知道可以使用机器学习领域中常用的核技巧(kernel trick)来避免计算图映射到特征空间的具体过程，从而简化计算，并且对于映射到无限维的特征空间中的情况下，使用Kernel几乎是唯一的选择。因此，一个合适的图kernel的选择可以带来图分类上的便利。

\subsection{核方法及其在机器学习中的作用}

Kernel-Based的机器学习方法通常认为kernel的用处在于将输入的数据非线性的做一个transform，将其映射到一个特征空间中去，从而可以在特征空间中容易的做推断(inference).

图\ref{fig:KernelUtil}就表现了这样的过程，显然输入空间中的数据是没有办法用一条直线将两类样本点直接分开的，然而通过映射$f:\mathbb{R}\mapsto \mathbb{R}, y = \sin{x}$我们就可以轻易的画出一条直线，从而让黑色的点位于1,2象限，其余的白色的点位于3,4象限。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=1\textwidth]{Img/kernelUtil.png}
    \caption{将原本输入空间中无法区分的数据映射到容易区分的特征空间中}
    \label{fig:KernelUtil}
\end{figure}
\subsection{基于随机游走的图核}

随机游走图kenel的想法就是我们对两个图都进行随机游走，然后比较得到的节点序列。

于是也可以将随机游走图kernel看作是在随机游走得到的序列上的kernel。

下面给出具体的定义:

\begin{definition}
    一个随机游走在图$\mathcal{G}$上以几率$p_s$从顶点$x_1\in\mathcal{V}$开始，从顶点$x_{i-1}$到顶点$x_i$的转移概率为$p_t(x_i|x_{i-1})$.而终止于顶点$x_l$的概率为$p_q$,从而一个随机游走的实例$x = x_1\dots x_l $发生的几率为:

    \begin{equation}\label{ProbRW}
        \mathbb{P}(x|\mathcal{G}) = p_{s}\left(x_{1}\right)\left(\prod_{i=2}^{l} p_{t}\left(x_{i} \mid x_{i-1}\right)\right) p_{q}\left(x_{l}\right) .
    \end{equation}

    一般我们认为随机游走的开始节点是等可能选择的，也就是,$p_s(v_i) = {|\mathcal{V} |}^{-1}$,而终止于顶点$v_i$的概率也一般设置为一个小的正数$c\in(0,1]$.
    
    而转移概率$p_t(v_i|x_{i-1})$我们设置为$\frac{1 - c}{d(x_{i-1})}$,其中$d(v)$表示节点$v$的度数，我们定义随机游走的标签序列$h_x = l(x_1)l(\{x_1,x_2\})\dots l(x_l)$,其中$l(\cdot)$表示一个节点或是一条边的标签。标签序列出现的概率是所有可能产生该标签序列的随机游走的概率总和，于是对于两个长度相同的标签序列上的kernel可以由几个标签kernel的乘积来定义:

    \begin{equation}\label{form:kernelZ}
        k_{z}\left(h_{x}, h_{x}^{\prime}\right)=k_{v}\left(h_{1}, h_{1}^{\prime}\right) \prod_{i=1}^{l-1} k_{e}\left(h_{2 i}, h_{2 i}^{\prime}\right) k_{v}\left(h_{2 i+1}, h_{2 i+1}^{\prime}\right) .
    \end{equation}

    其中$k_e,k_v$一般是半正定的kernel，从而可以得到上式定义的kernel是正定的\citep{KernelPDProof},对于不同长度的标签序列我们规定经过kernel得到的结果是0.

    于是我们可以定义出两个图上的随机游走图kernel为:在所有可能的标签序列上的标签序列kernel结果$k_z$的期望值。

    \begin{equation}\label{form:RWKernel}
        k(\mathcal{G},\mathcal{G}') = \sum_{h,h'} k_z(h,h')\mathbb{P}(h|\mathcal{G})\mathbb{P}(h'|\mathcal{G}')
    \end{equation}


\end{definition}

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=1\textwidth]{Img/RWexample.png}
    \caption{对两个分子结构图做random walk, 我们只考虑顶点的标签(原子类型),左图的随机游走得到的结果12131456,右图的随机游走得到的结果为53124689，这两种游走方式都可以得到相同的标签序列C0C0CCCC，如果考虑不同的边标签(共价键类型,s=single,d=double,a=aromatic)就可以诱导出不同的标签序列CdOdCsOsCsCsCsC和CsOsCsOsCaCaCaC}
    \label{fig:RWexample}
\end{figure}

\subsubsection{计算复杂度}
由\citep{ComputationalComplexity}知道，该方法可以在$O(n^3)$复杂度的情况下得到解，其中$n = \max({|\mathcal{V}|,|\mathcal{V}'|})$

\subsection{基于路径的图核}

基于路径的图kernel和随机游走图kernel很类似，但是采用了路径而不是随机游走得到的序列。

\begin{definition}
    记$P(\mathcal{G})$是图$\mathcal{G}$中的所有路径,我们记$k_z$是\ref{form:kernelZ}定义的kernel，于是可以定义全路径图kernel为:

    \begin{equation}
        k(\mathcal{G},\mathcal{G}') = \sum_{p\in P(\mathcal{G})\\ p' \in P(\mathcal{G}')} k_z(p,p')
    \end{equation}

\end{definition}

上面的kernel是正定的\citep{RConvKernel},然而，枚举一个图的所有路径是一个NP-hard的问题，因为这需要确定一个图是否存在一个Hamiltonian路径，同样的问题也存在于最长路径kernel中。

然而，最短路径我们可以在多项式的时间内计算出来，比如说使用Floyd-Warshall算法可以让我们在$O(|\mathcal{V}|^3)$的时间复杂度中计算出所有点对之间的最短路径。


    \begin{definition}
        记$\mathcal{G} = <\mathcal{V},\mathcal{E}>$是一个具有加权边的图，对应的最短路径图$\tilde{\mathcal{G}} = <\mathcal{V},\tilde{\mathcal{E}}>$,其中$\tilde{\mathcal{E}}$中的每条边都表示该边的两个端点之间具有一条路径，权值为路径的长度。从而我们可以定义最短路径图kernel为:
        
        \begin{equation}\label{form:ShortestPathKernel}
            k(\mathcal{G},\mathcal{G}') = \sum_{\tilde{e}\in \tilde{\mathcal{E}}\\\tilde{e}'\in \tilde{\mathcal{E}}'}k_e(\tilde{e},\tilde{e}')
        \end{equation}
        
    \end{definition}

    其中的$k_e$是作用在边上的kernel，我们排除带有负的边权的环，因为这会导致最短路的权值为负无穷。

    \subsubsection{计算复杂度}

    实践中，我们可以在$O(|\mathcal{V}|^4)$的时间复杂度\citep{RConvKernel}之内计算出公式\ref{form:ShortestPathKernel}. 甚至在某些情况下，得益于比较小的常数，最短路图kernel甚至还会比随机游走图kernel更快。 

\subsection{基于Graphlet的图核}
    Graphlet kernels一般是基于从图$\mathcal{G}$中对随机选择大小为$k\in\{3,4,5\}$的子图做计数。
    
    \begin{definition}
        我们记$\mathcal{G}_1,\dots,\mathcal{G}_N$表示一组大小为$k\in\{3,4,5\}$的子图，我们将图$\mathcal{G}$映射到特征空间中，通过下面的式子:
    
        \begin{equation}\label{form:GraphletMap}
            \phi(\mathcal{G})=\left(\#\left(\mathcal{G}_{1} \sqsubseteq \mathcal{G}\right), \ldots, \#\left(\mathcal{G}_{N} \sqsubseteq \mathcal{G}\right)\right)
        \end{equation}
    \end{definition}
    
        其中，$\# (H\sqsubseteq \mathcal{G})$表示$H$这种子图在$\mathcal{G}$中的计数。
    
        而Graphlet Kernel就是对在特征空间中的两个向量做内积，也就是:
    
        \begin{equation}\label{form:GraphletKernel}
            k(\mathcal{G},\mathcal{G}') = \langle \phi(\mathcal{G}),\phi (\mathcal{G}') \rangle
        \end{equation}

        有时候为了避免不同图的大小不同对kernel产生影响，我们会使用正则化了的kernel，也就是:

        \begin{equation}\label{form:NormGraphletKernel}
            k(\mathcal{G},\mathcal{G}') = \langle \|\phi(\mathcal{G})\|_{1}^{-1}\phi(\mathcal{G}),\|\phi (\mathcal{G}')\|_{1}^{-1}\phi (\mathcal{G}') \rangle
        \end{equation}

        \subsubsection{计算复杂度}
        计算公式\ref{form:GraphletMap}和\ref{form:NormGraphletKernel}需要计算所有
        $\left(\begin{array}{c}
            |\mathcal{V}| \\
            k
            \end{array}\right) = O(|\mathcal{V}|^k)$个graphlets.

\section{图神经网络介绍}

  2004年，Franco等人提出了第一种基于图的图神经网络(Graph Neural Network,GNN)\citep{firstGNN}模型，从那以后，各种不同的GNN模型相继被提出。2014年Bruna等人提出基于谱域上图傅里叶变换的图卷积神经网络(Graph Convolution Network,GCN)\citep{GCNFourier},这为后来的图神经网络提供了理论上的依据，同时，由于其存在各种不足，诸如计算效率低，无法局部化等等，也为后来的工作提供了很好的研究方向。

\subsection{图卷积神经网络}
\subsubsection{图Laplacian矩阵} 
在介绍经典的GCN之前，我们需要介绍一下图拉普拉斯矩阵。

\begin{definition}\label{def:graphLaplacian}
    对于图 $\mathcal{G} = <\mathcal{V} ,\mathcal{E} > $ 可以定义它的拉普拉斯矩阵:

    $\mathcal{L}$ = $\mathcal{D} - \mathcal{A}$, 其中$\mathcal{D}$是一个对角矩阵，$\mathcal{D}_{ii} = \sum_j \mathcal{A}_{ij} $, $\mathcal{A}$是图的邻接矩阵. 拉普拉斯矩阵的元素级定义为:

$$
    \mathcal{L}_{ij} = \left\{
        \begin{aligned}
        &deg(v_i) & i = j \\
        &-1 &e_{ij}\in \mathcal{E}  \\
        &0 & otherwise
        \end{aligned}
        \right.
$$

    拉普拉斯矩阵还有一种正则化了的形式(symmetric normalized laplacian) $\mathcal{L}_{sym} = \mathcal{D}^{-1/2}\mathcal{L}\mathcal{D}^{-1/2}$,其元素级别的定义如下: 

$$
\mathcal{L}_{ij} = \left\{
    \begin{aligned}
    &1 & i = j \\
    &\frac{-1}{\sqrt{deg(v_i)deg(v_j)}} &e_{ij}\in \mathcal{E}  \\
    &0 & otherwise
    \end{aligned}
    \right.
$$
\end{definition}


\begin{definition}\label{def:LaplacianFilter}
    在GCN中我们往往使用的是重归一化形式的拉普拉斯矩阵，其定义如下: 

    $$ \tilde{\mathcal{L}}_{sym} = \tilde{\mathcal{D}}^{-1/2} \tilde{\mathcal{A}} \tilde{\mathcal{D}}^{-1/2} $$
    
    其中$\tilde{\mathcal{A}} = \mathcal{A} + I, \tilde{\mathcal{D}}_{ii} = \sum_j \tilde{\mathcal{A}}_{ij}$ 
\end{definition}

拉普拉斯矩阵来源于拉普拉斯算子，是一个反应图上信号局部平滑度的算子

\subsubsection{图卷积神经网络}

假设我们有一个$n$个节点的图$ \mathcal{G} = <\mathcal{V} ,\mathcal{E}  >$,图中节点属性的矩阵$X \in \mathbb{R}^{n\times d} $, 图的邻接矩阵为$\mathcal{A}$,每一个节点可以被分类为$m$类中的一个。

上面的~\ref{def:LaplacianFilter} 实际上定义了一个滤波器，当我们将图信号矩阵$X$输入的时候，滤波器会得到一个响应 : 

$$
    X' = \tilde{\mathcal{L}}_{sym} X
$$

为了提高模型的拟合能力，可以对$X$做线性变换$Z = XW$后再送入滤波器中，也就是: 

$$
    X' = \sigma(\tilde{\mathcal{L}}_{sym} X W)
$$
其中$\sigma$是激活函数，上面这个式子就定义了图卷积的一层.

下面给出一个图卷积神经网络的简单例子: 

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{Img/GCN.png}
    \caption{简单的二层图卷积网络}
    \label{fig:GCN}
\end{figure}

首先，我们输入整个图的节点属性矩阵$X$和邻接矩阵$A$,通过一个两层图卷积网络，得到节点的embedding，$Z = ReLU(\tilde{\mathcal{L}}_{sym}ReLU(\tilde{\mathcal{L}}_{sym}XW_0)W_1)$，然后用$Softmax$函数输出预测的分类结果,$\hat{Y} = \text{softmax}(Z)$，最后在训练集的节点$\mathcal{V} _{train}$上比较预测结果$\hat{Y}$和真实标签$Y$的差距，计算交叉熵，将其作为损失函数，然后就可以通过随机梯度下降法训练模型，得到未知参数$W_0,W_1$。

\subsection{图注意力网络} 
    受到NLP领域中注意力(Attention)机制的启发，Veličković等人提出了GAT\citep{GAT}。

    注意力机制通过赋予输入不同的权重，来区分不同元素的重要性，从而可以提取出更关键的信息，得到更好的表征。

    下面我们介绍GAT的每一层是如何定义的，假设图$\mathcal{G}$有$N$个节点，作为输入的每个节点$i$的特征是$h_i\in \mathbb{R}^{F} $,通过这一层GAT更新后的节点特征为$h_i'$

    首先，通过一个共享的attention机制att来计算节点之间的权重:

        $$
            e_{ij} = \text{att}(Wh_i,Wh_j)
        $$
    其中，$W$是一个所有节点都共享的权重，将原本的节点特征由$F$维线性空间映射到$F'$维线性空间，再通过函数$\text{att}: \mathbb{R}^{F'} \mapsto \mathbb{R} $将其映射到一个实数域中，得到的结果$e_{ij}$就表示节点$j$相对于节点$i$而言的重要程度。在GAT中，我们通常选取一个单层全连接网络和一个$\text{LeakyReLU}$作为非线性激活函数来计算$e_{ij}$.具体而言如下:
        $$
            e_{ij} = \text{LeakyReLU}(\vec{a}[Wh_i\| Wh_j] )
        $$
    其中$\|$表示向量的拼接操作，$\vec{a}[Wh_i\| Wh_j]$则表示向量之间的内积。

    为了考虑图上的简单的结构信息，我们在计算不同节点之间的注意力权重时，只计算节点$i$的邻接点$\mathcal{N}_i$的权重，再做归一化，归一化后的注意力权重为:

        $$
            \alpha_{ij} = \text{Softmax}_j(e_{ij}) = \frac{\exp(e_{ij})}{\sum_{k\in\mathcal{N}_i}\exp(e_{ij})}
        $$

    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=0.4\textwidth]{Img/GATnodes.png}
        \caption{图上两个节点之间的attention过程，引自\citep{GAT}}
        \label{fig:GATnodes}
    \end{figure}

    基于这个注意力权重，考虑所有邻居节点的信息，我们可以得到更新后的新的节点特征:

        $$
            h_i' = \sigma(\sum_{j\in\mathcal{N}_i}\alpha_{ij}Wh_j)
        $$

    当然，也可以使用NLP领域中常用的多头机制，如图\ref{fig:GATFeature}

    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=0.4\textwidth]{Img/GATFeature.png}
        \caption{一层multi-head的GAT更新节点feature向量的过程,引自\citep{GAT}}
        \label{fig:GATFeature}
    \end{figure}

\section{图池化方法}
    池化(Pooling)是一个在卷积神经网络中常常使用的一种机制，在传统卷积神经网络中也可以称为下采样(Subsampling),池化层通常接在卷积层的后面，作用是保留显著特征，降低维度，减少参数量从而在一定程度上减轻过拟合。

    类似的，我们也可以仿照卷积神经网络中的池化，对池化节点邻域中的节点们做"下采样",目前常见的几种图上的池化机制可以分为下面几种:

    \begin{itemize}
        \item 基于图坍缩(Graph Coarsening)的池化: 将图划分成不同的子图，然后将子图视为超级节点，从而将图坍缩，实现对全局信息的一个融合。
        \item 基于TopK的池化: 对图中的每个节点学出一个分数，基于这个分数的排序丢弃一些得分较低的节点，类似于最大池化(MaxPooling).
        \item 基于边收缩(Edge Contraction)的池化: 通过归并操作，每次并行的将图中的边收缩，将被收缩的边两端的节点合并，从而逐步的学习到全局的信息。
    \end{itemize}

    本文中将主要介绍前两类方法的代表: DiffPool和TopKpool.

\subsection{DiffPool方法}
    DiffPool是首个提出可微分池化学习的方法，具体而言，首先通过一个GNN对每个节点做表征，然后通过另外一个GNN为每一个节点学习出所属于各个簇的概率分布，从数学表达来看，第$l$层的DiffPool所做的工作是:

    $$
        \begin{aligned}
            Z^{(l)} &= \text{GNN}_{l,embed}(\mathcal{A}^{(l)},\mathcal{H}^{(l)})
            \\
            S^{(l)} &= \text{Softmax}(\text{GNN}_{l,pool}(\mathcal{A}^{(l)},\mathcal{H}^{(l)}))
        \end{aligned}
    $$

    其中，$\mathcal{A}^{(l)} \in \mathbb{R}^{n_{(l)}\times n_{(l)}} ,S^{(l)}\in \mathbb{R}^{n_{(l)}\times n_{(l+1)}}$, $n_{(l)},n_{(l+1)}$分别表示第$l,l+1$层的节点数.

    $$
    \begin{aligned}
        \mathcal{H}^{(l+1)} &= {S^{(l)}}^T Z^{(l)}
        \\
        \mathcal{A}^{(l+1)} &= {S^{(l+1)}}^T\mathcal{A}^{(l)}S^{(l+1)}
    \end{aligned}
    $$

    上面的式子中，$Z^{(l)}$可以认为是得到的新的节点表征，而$S^{(l)}$则是用于图坍缩的簇分配矩阵，其作用是将下一层的邻接矩阵大小做坍缩，如图\ref{fig:diffpool}，原图经过几次图坍缩后变成了一个节点，从而将全局的信息汇合，可用于图分类。而从数学的角度来看:
    
    将上述公式所表示的过程成为一层DiffPool层，作用是:

    $$
        (\mathcal{A}^{(l)},Z^{(l)}) \mapsto (\mathcal{A}^{(l+1)},\mathcal{H}^{(l+1)})
    $$

    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=1\textwidth]{Img/diffpool.png}
        \caption{DiffPool的过程,引自\citep{DiffPool}}
        \label{fig:diffpool}
    \end{figure}

    有了上面对DiffPool的定义，我们就可以仿照CNN的分层模型设计结构，不断的堆叠GNN和DiffPool层，得到一个可微分的，层次化池化的学习机制，最终可以得到图的全局表示。


\subsection{TopK方法} 

    与DiffPool不同的是，TopKPooling并不期望通过一个簇分配矩阵来改变图的大小，而是期望通过丢弃重要性比较低的节点，来获得更小的并且保留更多重要信息的图，这一机制是一个不断丢弃节点的机制。

    具体来说，首先设置一个表示池化率的超参数$k\in (0,1)$,接着通过GNN学习出一个表示节点重要程度的值$z$,并通过对$z$做排序，将全图中$N$个节点下采样到$kN$个节点。

    
    这一系列过程如图~\ref{fig:topkpool},用数学公式表示如下:
    
    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=1\textwidth]{Img/topkpooling.png}
        \caption{TopKPool的过程,引自\citep{TopK}}
        \label{fig:topkpool}
    \end{figure}
    
    
    $$
        \begin{aligned}
            i &= \text{top-rank}({z},kN)\\
            X' &= X_{i,:}\\
            \mathcal{A}' &= \mathcal{A}_{i,i}
        \end{aligned}
    $$

    其中，$X_{i,:}$表示按照向量$i$做切片的特征矩阵，$\mathcal{A}_{i,j}$表示按照向量$i$对邻接矩阵$\mathcal{A}$同时做行切片和列切片。

    \section{本章小结}
        本章对本文涉及的相关工作做了简单的介绍，首先从复杂网络中常常可以从图的局部结构出现的频率来判断图的类别这一现象出发，介绍了Graphlets这一高阶图局部结构。
        
        接着本文介绍了几种传统的基于图核的图分类方法，如基于随机游走的图核、基于路径的图核、基于Graphlet的图核。
        
        再接着本文介绍了几种目前常用于图任务的图神经网络：图卷积神经网络，图注意力网络，也介绍了两种用于做分层池化的图池化方法，如DiffPool池化和Topk池化。
